package LeetCode;

import java.util.Stack;

public class LC_404_SumofLeftLeaves {

    public static void main(String[] args) {

    }

    class Solution {
        int sumOfLeftLeaves(TreeNode root, Boolean isLeft) {
            if (root == null) return 0;
            int sum = 0;
            if (root.left != null || root.right != null) {
                sum += sumOfLeftLeaves(root.left, true);
                sum += sumOfLeftLeaves(root.right, false);
            } else if (isLeft) sum += root.val;
            return sum;
        }

        public int sumOfLeftLeaves(TreeNode root) {
            return sumOfLeftLeaves(root, false);
        }

    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    class Solution_2 {
        public int sumOfLeftLeaves(TreeNode root) {
            if (root == null) return 0;
            int ans = 0;
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while (!stack.empty()) {
                TreeNode node = stack.pop();
                if (node.left != null) {
                    if (node.left.left == null && node.left.right == null)
                        ans += node.left.val;
                    else
                        stack.push(node.left);
                }
                if (node.right != null) {
                    if (node.right.left != null || node.right.right != null)
                        stack.push(node.right);
                }
            }
            return ans;
        }

    }
}